import java.util.LinkedList;
import java.util.Queue;

/**
 * @author SaoE
 * @date 2025/2/23 19:59
 */
public class _994 {
    public int orangesRotting(int[][] grid) {
        int res = 0;
        int m = grid.length;
        int n = grid[0].length;
        int countfresh = 0;
        int countEmpty = 0;
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                if (grid[i][j] == 2){
                    queue.offer(new int[]{i, j});
                }
                if(grid[i][j] == 0){
                    countEmpty++;
                }
                if(grid[i][j] == 1){
                    countfresh++;
                }
            }
        }
        if(queue.isEmpty()){
            if(countEmpty == 0){
                return -1;
            }
            if(countfresh == 0){
                return 0;
            }
        }
        int min = 0;
        while(!queue.isEmpty()){
            min++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] poll = queue.poll();
                int row = poll[0];
                int col = poll[1];
                if (row - 1 >= 0 && grid[row - 1][col] == 1){
                    grid[row - 1][col] = 2;
                    queue.offer(new int[]{row - 1, col});
                }
                if (row + 1 < m && grid[row + 1][col] == 1){
                    grid[row + 1][col] = 2;
                    queue.offer(new int[]{row + 1, col});
                }
                if (col - 1 >= 0 && grid[row][col - 1] == 1){
                    grid[row][col - 1] = 2;
                    queue.offer(new int[]{row, col - 1});
                }
                if (col + 1 < n && grid[row][col + 1] == 1){
                    grid[row][col + 1] = 2;
                    queue.offer(new int[]{row, col + 1});
                }

            }
        }
        min--;
        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                if (grid[i][j] == 1){
                    return -1;
                }
            }
        }
        return min;
    }

    public static void main(String[] args) {
        _994 a = new _994();
        int[][] grid = {{2,1,1},{1,1,0},{0,1,1}};
        System.out.println(a.orangesRotting(grid));
    }
}
